/*******************************************************************************
 * Includes
 ******************************************************************************/
#include "Wed_slab.h"

/*******************************************************************************
 * Static
 ******************************************************************************/
static unsigned long             __g_heap_start, __g_heap_end;
static struct Wed_slab_page_hdr *__g_p_page_list;
static int                       __g_zone_size;
static int                       __g_zone_limit;
static int                       __g_zone_page_cnt;
static int                       __g_zone_free_cnt;
static struct Wed_slab_memusage *__g_p_memusage = NULL;
static struct Wed_slab_zone     *__g_p_zone_array[WED_SLAB_MAX_N_ZONES];
static struct Wed_slab_zone     *__g_p_zone_free;
static struct Wed_mutex          __g_slab_mutex;

#if WED_MEM_STATS
static unsigned long             __g_used_mem, __g_max_mem;
#endif

/*******************************************************************************
 * Macro operate
 ******************************************************************************/
#define btokup(addr)    \
    (&__g_p_memusage[((unsigned long)(addr) - __g_heap_start) >> WED_SLAB_PAGE_BITS])

/*******************************************************************************
 * Code
 ******************************************************************************/
/**
 * \brief slab 页分配
 *
 * @param n_pages 要分配的页数量
 *
 * \retval 成功返回分配的页起始地址
 */
void *Wed_slab_page_alloc(unsigned long n_pages){
    int                        ret;
    struct Wed_slab_page_hdr  *p_b, *p_n;
    struct Wed_slab_page_hdr **p_prev;

    if (n_pages == 0) {
        return NULL;
    }

    ret = Wed_mutex_lock(&__g_slab_mutex, 5000);
    if (ret != 0) {
        return NULL;
    }
    /* 遍历页信息 */
    for (p_prev = &__g_p_page_list; (p_b = *p_prev) != NULL; p_prev = &(p_b->p_next)) {
        if (p_b->page > n_pages) {
            /* 拆分页 */
            p_n         = p_b + n_pages;
            p_n->p_next = p_b->p_next;
            p_n->page   = p_b->page - n_pages;
            *p_prev     = p_n;
            break;
        }

        /* 刚好合适，获取当前的页 */
        if (p_b->page == n_pages) {
            *p_prev = p_b->p_next;
            break;
        }
    }

    Wed_mutex_unlock(&__g_slab_mutex);

    return p_b;
}

/**
 * \brief slab 页释放
 *
 * @param p_addr  页起始地址
 * @param n_pages 释放的页数量
 */
void Wed_slab_page_free(void *p_addr, unsigned long n_pages){
    int                        ret;
    struct Wed_slab_page_hdr  *p_b, *p_n;
    struct Wed_slab_page_hdr **p_prev;

    if ((p_addr == NULL) ||
            ((unsigned long)p_addr % WED_SLAB_PAGE_SIZE) ||
            (n_pages == 0)) {
        return;
    }

    p_n = (struct Wed_slab_page_hdr *)p_addr;

    ret = Wed_mutex_lock(&__g_slab_mutex, 5000);
    if (ret != 0) {
        return;
    }
    /* 遍历页信息链表 */
    for (p_prev = &__g_p_page_list; (p_b = *p_prev) != NULL; p_prev = &(p_b->p_next)) {
        /* 是否能与当前页向后合并 */
        if (p_b + p_b->page == p_n) {
            /* 是否能继续向后合并下一个页 */
            if (p_b + (p_b->page += n_pages) == p_b->p_next) {
                /* 合并下一个页 */
                p_b->page   += p_b->p_next->page;
                /* 移除下一个页 */
                p_b->p_next  = p_b->p_next->p_next;
            }

            goto __exit;
        }
        /* 是否能往前合并页 */
        if (p_b == p_n + n_pages) {
            p_n->page   = p_b->page + n_pages;
            p_n->p_next = p_b->p_next;
            *p_prev     = p_n;

            goto __exit;
        }

        if (p_b > p_n + n_pages)
            break;
    }

    p_n->page   = n_pages;
    p_n->p_next = p_b;
    *p_prev     = p_n;

__exit:
    Wed_mutex_unlock(&__g_slab_mutex);
}

/**
 * \brief 内存页初始化
 */
static void __page_init(void *p_addr, unsigned long n_pages){
    __g_p_page_list = NULL;
    /* 初始化内存页 */
    Wed_slab_page_free(p_addr, n_pages);
}

/**
 * \brief slab 初始化
 *
 * @param p_begin_addr 内存起始地址
 * @param size         内存大小
 *
 * \retval 成功返回 0
 */
int Wed_slab_init(void *p_begin_addr, unsigned long size){
    int           ret;
    unsigned long limit_size, n_pages;

    if ((p_begin_addr == NULL) || (size == 0)) {
        return -WED_EINVAL;
    }

    /* 页对齐 */
    __g_heap_start = WED_ALIGN((unsigned long)p_begin_addr, WED_SLAB_PAGE_SIZE);
    __g_heap_end   = WED_ALIGN_DOWN((unsigned long)(p_begin_addr + size), WED_SLAB_PAGE_SIZE);
    /* 计算内存大小 */
    limit_size = __g_heap_end - __g_heap_start;
    /* 计算页总数量 */
    n_pages    = limit_size / WED_SLAB_PAGE_SIZE;
    /* 初始化互斥锁 */
    ret = Wed_mutex_init(&__g_slab_mutex);
    if (ret != 0) {
        return ret;
    }

    WED_INFO_PRINT("slab heap[0x%x - 0x%x], size %d bytes, %d pages\r\n",
            __g_heap_start, __g_heap_end, limit_size, n_pages);

    /* 把内存初始化成一个个页 */
    __page_init((void *)__g_heap_start, n_pages);

    __g_zone_size = WED_SLAB_MIN_ZONE_SIZE;
    /* 计算 zone 大小 */
    while ((__g_zone_size < WED_SLAB_MAX_ZONE_SIZE) &&
            ((__g_zone_size << 1) < (limit_size / 1024))) {
        __g_zone_size <<= 1;
    }

    __g_zone_limit = __g_zone_size / 4;
    if (__g_zone_limit > WED_SLAB_ZONE_LIMIT) {
        __g_zone_limit = WED_SLAB_ZONE_LIMIT;
    }
    /* 一个 zone 包含的页数量 */
    __g_zone_page_cnt = __g_zone_size / WED_SLAB_PAGE_SIZE;

    WED_DEBUG_PRINT("slab zone size %d bytes, zone page count %d\r\n",
                                 __g_zone_size, __g_zone_page_cnt);

    /* 初始化页管理器，每个页都有一个页管理器 */
    limit_size     = n_pages * sizeof(struct Wed_slab_memusage);
    limit_size     = WED_ALIGN(limit_size, WED_SLAB_PAGE_SIZE);
    __g_p_memusage = Wed_slab_page_alloc(limit_size / WED_SLAB_PAGE_SIZE);

    WED_DEBUG_PRINT("slab memusage 0x%x, size %d bytes\r\n", (unsigned long)__g_p_memusage, limit_size);

    return 0;
}

/**
 * \brief 根据内存大小获取 zone 索引
 *        申请内存小于 128 字节，zone 从 8 字节开始，往后 8 字节递增
 *        zone[0] = 8，zone[1] = 16...zone[15] = 128
 *        申请内存小于 256 字节，zone 从 144 字节开始，往后 16 字节递增
 *        zone[16] = 144，zone[17] = 160...zone[23] = 256
 *        申请内存小于 512 字节，zone 从 288 字节开始，往后 32 字节递增
 *        zone[24] = 288，zone[25] = 320...zone[31] = 512
 *        申请内存小于 1024 字节，zone 从 576 字节开始，往后 64 字节递增
 *        zone[32] = 576，zone[33] = 640...zone[39] = 1024
 *        申请内存小于 2048 字节，zone 从 1152 字节开始，往后 128 字节递增
 *        zone[40] = 1152，zone[41] = 1280...zone[47] = 2048
 *        申请内存小于 4096 字节，zone 从 2304 字节开始，往后 256 字节递增
 *        zone[48] = 2304，zone[49] = 2560...zone[55] = 4096
 *        申请内存小于 8192 字节，zone 从 4608 字节开始，往后 512 字节递增
 *        zone[56] = 4608，zone[57] = 5120...zone[63] = 8192
 *        申请内存小于 16384 字节，zone 从 4608 字节开始，往后 1024 字节递增
 *        zone[64] = 9216，zone[57] = 10240...zone[71] = 16384
 */
static int __zone_index(unsigned long *p_bytes){
    /* unsigned for shift opt */
    unsigned long n = (unsigned long)(*p_bytes);

    if (n < 128) {
        /* 一个 chunk 8 字节，8 字节对齐 */
        *p_bytes = n = (n + 7) & ~7;

        return (n / 8 - 1);
    } if (n < 256) {
        /* 一个 chunk 16 字节，16 字节对齐 */
        *p_bytes = n = (n + 15) & ~15;

        return (n / 16 + 7);
    }
    if (n < 8192) {
        if (n < 512) {
            *p_bytes = n = (n + 31) & ~31;

            return (n / 32 + 15);
        }
        if (n < 1024) {
            *p_bytes = n = (n + 63) & ~63;

            return (n / 64 + 23);
        }
        if (n < 2048) {
            *p_bytes = n = (n + 127) & ~127;

            return (n / 128 + 31);
        }
        if (n < 4096) {
            *p_bytes = n = (n + 255) & ~255;

            return (n / 256 + 39);
        }
        *p_bytes = n = (n + 511) & ~511;

        return (n / 512 + 47);
    }
    if (n < 16384) {
        *p_bytes = n = (n + 1023) & ~1023;

        return (n / 1024 + 55);
    }

    return 0;
}

/**
 * \brief slab 内存分配
 *
 * @param size 要分配的内存大小
 *
 * \retval 成功返回分配的内存起始地址
 */
void *Wed_slab_mem_alloc(unsigned long size){
    int                       ret;
    int32_t                   zi, off;
    struct Wed_slab_zone     *p_z     = NULL;
    struct Wed_slab_chunk    *p_chunk = NULL;
    struct Wed_slab_memusage *p_kup   = NULL;

    if (size == 0) {
        return NULL;
    }

    /* 分配大内存 */
    if (size >= __g_zone_limit) {
        /* 对齐页大小 */
        size = WED_ALIGN(size, WED_SLAB_PAGE_SIZE);

        ret = Wed_mutex_lock(&__g_slab_mutex, 5000);
        if (ret != 0) {
            return NULL;
        }

        /* 分配页 */
        p_chunk = Wed_slab_page_alloc(size >> WED_SLAB_PAGE_BITS);
        if (p_chunk == NULL) {
            goto __done;
        }

        /* 获取对应的页管理器 */
        p_kup      = btokup(p_chunk);
        p_kup->type = WED_SLAB_PAGE_TYPE_LARGE;
        p_kup->size = size >> WED_SLAB_PAGE_BITS;

        WED_DEBUG_PRINT("slab malloc a large memory %d bytes, page cnt %d, kup %d\r\n",
                         size,
                         size >> WED_SLAB_PAGE_BITS,
                       ((unsigned long)p_chunk - __g_heap_start) >> WED_SLAB_PAGE_BITS);

#if WED_MEM_STATS
        __g_used_mem += size;
        if (__g_used_mem > __g_max_mem) {
            __g_max_mem = __g_used_mem;
        }
#endif
        goto __done;
    }

    ret = Wed_mutex_lock(&__g_slab_mutex, 5000);
    if (ret != 0) {
        return NULL;
    }
    /* 根据申请的内存获取 zone 索引 */
    zi = __zone_index(&size);

    if (zi > WED_SLAB_MAX_N_ZONES) {
        goto __done;
    }

    WED_DEBUG_PRINT("slab try to malloc %d bytes on zone %d\r\n", size, zi);

    /* 已经分配的 zone */
    if ((p_z = __g_p_zone_array[zi]) != NULL) {
        if (p_z->z_nfree <= 0) {
            return NULL;
        }
        /* 没内存块了，从全局 zone 数组中移除 */
        if (--p_z->z_nfree == 0) {
            __g_p_zone_array[zi] = p_z->p_z_next;
            p_z->p_z_next = NULL;
        }

        if (p_z->z_uindex + 1 != p_z->z_nmax) {
            /* 分配索引还没到最后了，直接根据索引分配 */
            p_z->z_uindex = p_z->z_uindex + 1;
            p_chunk = (struct Wed_slab_chunk *)(p_z->p_z_baseptr + p_z->z_uindex * size);
        } else {
            /* 分配索引已经到最后了，从空闲内存块链表中获取内存块 */
            p_chunk = p_z->p_z_freechunk;

            /* 移除空闲的内存块 */
            p_z->p_z_freechunk = p_z->p_z_freechunk->p_c_next;
        }

#if WED_MEM_STATS
        __g_used_mem += p_z->z_chunksize;
        if (__g_used_mem > __g_max_mem) {
            __g_max_mem = __g_used_mem;
        }
#endif

        goto __done;
    }

    if ((p_z = __g_p_zone_free) != NULL) {
        /* 获取空闲 zone 链表中的 zone */
        __g_p_zone_free = p_z->p_z_next;
        --__g_zone_free_cnt;
    } else {
        /* 先释放互斥锁，因为分配页的时候会使用互斥锁 */
        Wed_mutex_unlock(&__g_slab_mutex);

        /* 分配 zone */
        p_z = Wed_slab_page_alloc(__g_zone_page_cnt);
        if (p_z == NULL) {
            p_chunk = NULL;
            goto __exit;
        }

        ret = Wed_mutex_lock(&__g_slab_mutex, 5000);
        if (ret != 0) {
            return NULL;
        }

        WED_DEBUG_PRINT("slab alloc a new zone 0x%x\r\n", (unsigned long)p_z);

        /* 设置页在 zone 中的偏移 */
        for (off = 0, p_kup = btokup(p_z); off < __g_zone_page_cnt; off++) {
            p_kup->type = WED_SLAB_PAGE_TYPE_SMALL;
            p_kup->size = off;

            p_kup++;
        }
    }

    memset(p_z, 0, sizeof(struct Wed_slab_zone));

    /* 可用内存在 zone 中的偏移 */
    off = sizeof(struct Wed_slab_zone);

    /* 确保 2 的幂大小的内存块是 2 的幂次对齐，否则按 8 字节 对齐 */
    if ((size | (size - 1)) + 1 == (size << 1)) {
        off = (off + size - 1) & ~(size - 1);
    } else {
        off = (off + WED_SLAB_MIN_CHUNK_MASK) & ~WED_SLAB_MIN_CHUNK_MASK;
    }
    p_z->z_magic     = WED_SLAB_MAGIC;
    p_z->z_zoneindex = zi;
    p_z->z_nmax      = (__g_zone_size - off) / size;
    p_z->z_nfree     = p_z->z_nmax - 1;
    p_z->p_z_baseptr = (uint8_t *)p_z + off;
    p_z->z_uindex    = 0;
    p_z->z_chunksize = size;

    p_chunk = (struct Wed_slab_chunk *)(p_z->p_z_baseptr + p_z->z_uindex * size);

    /* 链接到 zone 全局数组中 */
    p_z->p_z_next = __g_p_zone_array[zi];
    __g_p_zone_array[zi] = p_z;

#if WED_MEM_STATS
    __g_used_mem += p_z->z_chunksize;
    if (__g_used_mem > __g_max_mem) {
        __g_max_mem = __g_used_mem;
    }
#endif

__done:
    Wed_mutex_unlock(&__g_slab_mutex);

__exit:
    return p_chunk;
}

/**
 * \brief slab 内存释放
 *
 * @param p_mem 要释放的内存地址
 */
void Wed_slab_mem_free(void *p_mem){
    struct Wed_slab_zone      *p_z     = NULL;
    struct Wed_slab_zone     **p_z_tmp = NULL;
    struct Wed_slab_chunk     *p_chunk = NULL;
    struct Wed_slab_memusage  *p_kup   = NULL;
    unsigned long              size;
    int                        ret;

    if (p_mem == NULL) {
        return ;
    }

    /* get memory usage */
#if RT_DEBUG_SLAB
    {
        rt_ubase_t addr = ((rt_ubase_t)ptr & ~RT_MM_PAGE_MASK);
        RT_DEBUG_LOG(RT_DEBUG_SLAB,
                     ("free a memory 0x%x and align to 0x%x, kup index %d\n",
                      (rt_ubase_t)ptr,
                      (rt_ubase_t)addr,
                      ((rt_ubase_t)(addr) - heap_start) >> RT_MM_PAGE_BITS));
    }
#endif

    /* 4K 对齐 */
    p_kup = btokup((unsigned long)p_mem & ~WED_SLAB_PAGE_MASK);
    /* 释放大内存 */
    if (p_kup->type == WED_SLAB_PAGE_TYPE_LARGE) {

        ret = Wed_mutex_lock(&__g_slab_mutex, 5000);
        if (ret != 0) {
            return;
        }
        /* clear page counter */
        size = p_kup->size;
        p_kup->size = 0;

#ifdef WED_MEM_STATS
        __g_used_mem -= size * WED_SLAB_PAGE_SIZE;
#endif
        Wed_mutex_unlock(&__g_slab_mutex);

        WED_DEBUG_PRINT("slab free large memory block 0x%x, page count %d\r\n",
                        (unsigned long)p_mem, size);

        /* 释放页 */
        Wed_slab_page_free(p_mem, size);

        return;
    }

    ret = Wed_mutex_lock(&__g_slab_mutex, 5000);
    if (ret != 0) {
        return;
    }

    /* 定位到 zone 的起始位置 */
    p_z = (struct Wed_slab_zone *)(((unsigned long)p_mem & ~WED_SLAB_PAGE_MASK) -
                      p_kup->size * WED_SLAB_PAGE_SIZE);
    if (p_z->z_magic != WED_SLAB_MAGIC) {
        WED_ERR_PRINT("memory block of slab zone magic 0x%x illegal\r\n", p_z->z_magic);
        goto __exit;
    }

    /* 把要释放的内存链接进 zone 的空闲内存块链表 */
    p_chunk            = (struct Wed_slab_chunk *)p_mem;
    p_chunk->p_c_next  = p_z->p_z_freechunk;
    p_z->p_z_freechunk = p_chunk;

#ifdef WED_MEM_STATS
    __g_used_mem -= p_z->z_chunksize;
#endif

    /* 又有空闲块可以用，把 zone 链接回链表中 */
    if (p_z->z_nfree++ == 0) {
        p_z->p_z_next = __g_p_zone_array[p_z->z_zoneindex];
        __g_p_zone_array[p_z->z_zoneindex] = p_z;
    }

    /* 如果当前 zone 完全空闲，且我们还有其他 zone 可分配，则将当前 zone 移除 zone 链表 */
    if ((p_z->z_nfree == p_z->z_nmax) &&
        ((p_z->p_z_next) || (__g_p_zone_array[p_z->z_zoneindex] != p_z))) {

        WED_DEBUG_PRINT("slab free zone %d, 0x%x\r\n", p_z->z_zoneindex, (unsigned long)p_z);

        /* 找到当前 zone 的位置 */
        for (p_z_tmp = &__g_p_zone_array[p_z->z_zoneindex]; p_z != *p_z_tmp; p_z_tmp = &(*p_z_tmp)->p_z_next)
            ;
        /* 移除链表 */
        *p_z_tmp = p_z->p_z_next;

        /* 复位 zone */
        p_z->z_magic = -1;

        /* 插入空闲 zone 链表 */
        p_z->p_z_next = __g_p_zone_free;
        __g_p_zone_free = p_z;

        ++__g_zone_free_cnt;

        /* 释放空闲的 zone 到页分配器 */
        if (__g_zone_free_cnt > WED_SLAB_ZONE_RELEASE_THRESH) {
            register unsigned long i;

            p_z             = __g_p_zone_free;
            __g_p_zone_free = p_z->p_z_next;
            --__g_zone_free_cnt;

            /* 复位页管理器 */
            for (i = 0, p_kup = btokup(p_z); i < __g_zone_page_cnt; i++) {
                p_kup->type = WED_SLAB_PAGE_TYPE_FREE;
                p_kup->size = 0;
                p_kup++;
            }

            Wed_mutex_unlock(&__g_slab_mutex);

            /* 释放页 */
            Wed_slab_page_free(p_z, __g_zone_size / WED_SLAB_PAGE_SIZE);

            return;
        }
    }
__exit:
    Wed_mutex_unlock(&__g_slab_mutex);
}
